/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/fibonacci-ii
   @Language: C++
   @Datetime: 19-05-18 14:39
   */

class Solution {
	void multimod(int f1[2][2], int f2[2][2], int res[2][2]){
		int tmp[2][2];
		tmp[0][0]=(f1[0][0]*f2[0][0]+f1[0][1]*f2[1][0])%10000;
		tmp[0][1]=(f1[0][0]*f2[0][1]+f1[0][1]*f2[1][1])%10000;
		tmp[1][0]=(f1[1][0]*f2[0][0]+f1[1][1]*f2[1][0])%10000;
		tmp[1][1]=(f1[1][0]*f2[0][1]+f1[1][1]*f2[1][1])%10000;
		res[0][0]=tmp[0][0];
		res[0][1]=tmp[0][1];
		res[1][0]=tmp[1][0];
		res[1][1]=tmp[1][1];
	}
public:
	/**
	 * @param n: an integer
	 * @return: return a string
	 */
	string lastFourDigitsOfFn(int n) {
		// write your code here
		if(n==0) return "0";
		int f0[2][2]={{1,1},{1,0}}, fn[2][2]={{1,0},{0,1}};
		for(; n; n>>=1){
			if(n&1) multimod(f0,fn,fn);
			multimod(f0,f0,f0);
		}
		char str[5];
		sprintf(str,"%04d",fn[0][1]);
		return str;
	}
};
